package LeetCode.month01.day19;

import java.util.Arrays;

public class No1143 {
    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("bsbininm", "jmjkbkjkv"));
    }
    public static int longestCommonSubsequence(String text1, String text2) {
        int m =text1.length();
        int n = text2.length();
        if(m>=n) {
            int[] dp = new int[n+1];
            System.out.println("    "+Arrays.toString(text2.toCharArray()));
            for (int i = 1; i <= m; i++) {
                if(i>1)System.out.print(text1.charAt(i-1));
                else System.out.print(" ");
                int pre = 0;//存储dp[j]修改前的数，因为在i++之后，dp数组相当于存储的就是上一行的值，存储的相当于等于dp[i-1][j-1]
                for (int j = 1; j <=n; j++) {
                    int temp = dp[j];
                    if(text1.charAt(i-1)==text2.charAt(j-1)){
                        dp[j]=pre+1;
                    }else{
                        dp[j]=Math.max(dp[j-1],dp[j]);
                    }
                    pre = temp;
                }
                System.out.println(Arrays.toString(dp));
            }
            //System.out.println(Arrays.toString(dp));
            return dp[n];
        }
        else {
            return longestCommonSubsequence(text2,text1);
        }
    }
}
